package com.yusong.algorithm.array;


import com.yusong.algorithm.util.PrintUtils;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.stream.Collectors;

public class Permute46 {

    public static void main(String[] args) {

        Permute46 main = new Permute46();
        int[] datas = {1,2,3};
        main.permute(datas);
    }


    /**
     回溯法遍历
     数组处理方法1.转化为List
     **/
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new LinkedList<>();
        List<Integer> remainNums = new LinkedList<>();
        for(int index = 0; index< nums.length; index++){
            remainNums.add(nums[index]);
        }
        recurseOrder(remainNums, new LinkedList(), res);
        return res;
    }

    /**
     remainNums 剩余的数据
     preTmpRes 之前排序的中间结果
     res 汇总的结果
     **/
    private void recurseOrder(List<Integer> remainNums, List<Integer> preTmpRes, List<List<Integer>> res){
        //终止条件
        if(remainNums.size() == 0){
            res.add(new LinkedList(preTmpRes));
            return;
        }
        //中间过程
        int length = remainNums.size();
        for(int i = 0; i< length; i++){
            Integer data = remainNums.get(i);
            //递归前操作
            remainNums.remove(data);
            preTmpRes.add(data);
            //递归
            //System.out.println(PrintUtils.list2Str(remainNums));
            recurseOrder(remainNums, preTmpRes, res);
            //回溯还原现场
            //防止打乱顺序
            remainNums.add(i,data);
            preTmpRes.remove(data);
        }
    }
}
